//
//  tree_demo.hpp
//  cpp_algorithm
//
//  Created by 李贺 on 2022/1/13.
//

#ifndef tree_demo_hpp
#define tree_demo_hpp

#include <stdio.h>
#include <vector>
#include <iostream>
#include <string>
#include <unordered_map>
#include <stack>
#include <queue>
using namespace std;

struct TreeNode {
    TreeNode *left;
    TreeNode *right;
    int val;
    TreeNode(int x): val(x), left(NULL),right(NULL) {
        
    }
};

// 二叉树前中后 遍历
namespace pre_traval_demo {
class Solution {
public:
    
    void pre_traversal(TreeNode * cur,vector<int> &vec) {
        if (cur == NULL) {
            return;
        }
        vec.push_back(cur->val);
        pre_traversal(cur->left, vec);
        pre_traversal(cur->right, vec);
    }
    
    vector<int> preOrderTraversal(TreeNode*rootnode){
        vector<int> vec;
        pre_traversal(rootnode, vec);
        return vec;
    }
    
    void middle_traversal(TreeNode * cur,vector<int> vec) {
        if (cur == NULL) {
            return;
        }
        middle_traversal(cur->left, vec);
        vec.push_back(cur->val);
        middle_traversal(cur->right, vec);
    }
    
    vector<int> middleOrderTraversal(TreeNode *rootnode) {
        vector<int> vec;
        middle_traversal(rootnode, vec);
        return vec;
    }
    
    void post_traversal(TreeNode * cur,vector<int> vec) {
        if (cur == NULL) {
            return;
        }
        post_traversal(cur->left, vec);
        post_traversal(cur->right, vec);
        vec.push_back(cur->val);
    }
    
    vector<int> postOrderTraversal(TreeNode *rootnode) {
        vector<int> vec;
        post_traversal(rootnode, vec);
        return vec;
    }
};
}

// 利用栈实现的非递归深度遍历, 前序遍历
namespace tree_stack_traversal_space {
class Solution {
public:
    // 前序遍历
    vector<int> pre_traversal(TreeNode *rootNode) {
        
        vector<int> result;
        if (rootNode == nullptr) {
            return result;
        }
        
        stack<TreeNode*> st;
        st.push(rootNode);
        
        while (st.empty() == false) {
            
            TreeNode *node = st.top();
            result.push_back(node->val);
            st.pop();
            // 进两个, 出一个, 所以能实现想递归一样的算法
            if (node->right) {
                st.push(node->right);
            }
            
            if (node->left) {
                st.push(node->left);
            }
        }
        
        return result;
    }
    
    // 中序遍历
    vector<int> middle_traversal(TreeNode *root) {
        
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode *cur = root;
        
        while (cur || !st.empty()) {
            if (cur) {
                st.push(cur);
                cur = cur->left;
            } else {
                cur = st.top();
                st.pop();
                result.push_back(cur->val);
                cur = cur->right;
            }
        }
        return result;
    }
    
    // 后续遍历是前序遍历的倒叙
    vector<int> post_traversal(TreeNode *root) {
        
        vector<int> result;
        stack<TreeNode*> st;
        st.push(root);
        
        while (st.empty() == false) {
            
            TreeNode *node = st.top();
            result.push_back(node->val);
            st.pop();
            
            if (node->left) {
                st.push(node->left);
            }
            
            // 进两个, 出一个, 所以能实现想递归一样的算法
            if (node->right) {
                st.push(node->right);
            }
        }
        
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
    }
    
};
}


// 二叉树 层级遍历
namespace tree_queue_traversal_space {
class Solution {
public:
    vector<vector<int>> lever_order_traversal(TreeNode *root){
        vector<vector<int>> result;
        queue<TreeNode*> qu;
        if (root == nullptr) {
            return result;
        }
        
        qu.push(root);
        while (!qu.empty()) {
            int size = (int)qu.size();
            vector<int> vec;
            
            for (int i = 0; i < size; ++i) {
                TreeNode *node = qu.front();
                qu.pop();
                vec.push_back(node->val);
                if (node->left) {
                    qu.push(node->left);
                }
                if (node->right) {
                    qu.push(node->right);
                }
            }
            result.push_back(vec);
        }
        
        return result;
    }
};
}

// 翻转二叉树
namespace tree_flip_space {
class Solution {
public:
    TreeNode * flip_tree(TreeNode*root) {
        if (root == NULL) {
            return root;
        }
        
        swap(root->left, root->right);
        flip_tree(root->left);
        flip_tree(root->right);
        
        return root;
    }
};

class Solution1 {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right); // 节点处理
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return root;
    }
};

class Solution2 {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            swap(node->left, node->right);
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};

}

//二叉树对称
namespace tree_symmetry_eachother {

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root->left);   // 将左子树头结点加入队列
        que.push(root->right);  // 将右子树头结点加入队列
        
        while (!que.empty()) {  // 接下来就要判断这两个树是否相互翻转
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (leftNode == nullptr && rightNode == nullptr) {  // 左节点为空、右节点为空，此时说明是对称的
                continue;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if ((leftNode == nullptr || rightNode == nullptr || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   // 加入左节点左孩子
            que.push(rightNode->right); // 加入右节点右孩子
            que.push(leftNode->right);  // 加入左节点右孩子
            que.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};
}

// 二叉树最大深度
namespace tree_max_deepth {
class Solution {
public:
    int get_deepth(TreeNode *node) {
        if (node == NULL) {
            return 0;
        }
        
        int leftValue = get_deepth(node->left);
        int rightValue = get_deepth(node->right);
        int max_dep = 1 + max(leftValue, rightValue);
        return max_dep;
    }
    
    int tree_max_deepth(TreeNode *root) {
        if (root == NULL) {
            return 0;
        }
        int maxdep = get_deepth(root);
        return maxdep;
    }
};

class Solution1 {
public:
    int level_traversal(TreeNode *root) {
        if (root == NULL) {
            return 0;
        }
        
        queue<TreeNode*> qu;
        int result = 0;
        qu.push(root);
        
        while (qu.empty() == false) {
            
            int size = static_cast<int>(qu.size());
            
            // 每次有多少个就出空
            for (int i = 0; i < size; ++i) {
                TreeNode * node = qu.front();
                qu.pop();
                
                if (node->left) {
                    qu.push(node->left);
                }
                if (node->right) {
                    qu.push(node->right);
                }
            }
            ++result;
        }
        
        return result;
    }
};
}

namespace tree_min_deepth {
class Solution {
public:

    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = static_cast<int>(que.size());
            depth++; // 记录最小深度
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出
                    return depth;
                }
            }
        }
        return depth;
    }
};
}

// 二叉树是不是平衡二叉树
namespace tree_banlance {

class Solution {
public:
    
    int tree_deepth(TreeNode *node) {
        if (node == NULL) {
            return 0;
        }
        
        int leftHeight = tree_deepth(node->left);
        if (leftHeight == -1) {
            return -1;
        }
        
        int rightHeight = tree_deepth(node->right);
        if (rightHeight == -1) {
            return -1;
        }
        
        int det = abs(leftHeight - rightHeight);
        if (det > 1) {
            return -1;
        }
        return 1 + max(leftHeight,rightHeight);
    }
    
    bool tree_banlance(TreeNode*root) {
        if (root == NULL) {
            return true;
        }
        
        int dep = tree_deepth(root);
        return dep != -1;
    }
};

}

// 二叉树的路径的数量
namespace tree_path {

class Solution {
    
public:
    
    vector<string> tree_path(TreeNode *root) {
        vector<string> result;
        
        if (root == NULL) {
            return result;
        }
        
        stack<TreeNode*> nodeSt;
        nodeSt.push(root);
        
        stack<string> pathSt;
        pathSt.push(to_string(root->val));
        
        while (nodeSt.empty() == false) {
            
            TreeNode *node = nodeSt.top();
            nodeSt.pop();
            
            string path = pathSt.top();
            pathSt.pop();
            
            if (node->left == NULL && node->right == NULL) {
                result.push_back(path);
            }
            
            if (node->right) {
                nodeSt.push(node->right);
                pathSt.push(path + "->" + to_string(node->right->val));
            }
            
            if (node->left) {
                nodeSt.push(node->left);
                pathSt.push(path + "->" + to_string(node->left->val));
            }
            
        }
        
        return result;
    }
    
};

}

namespace tree_left_leaf_sum {

class Solution{
public:
    int left_sum(TreeNode *node) {
        if (node == NULL) {
            return 0;
        }
        
        int leftValue = left_sum(node->left);
        int rightValue = left_sum(node->right);
        int middle = 0;
        if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
            middle = node->left->val;
        }
        int sum = leftValue + rightValue + middle;
        return sum;
    }
};

class Solution1 {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        stack<TreeNode*> st;
        if (root == NULL) return 0;
        st.push(root);
        int result = 0;
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
                result += node->left->val;
            }
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return result;
    }
};

}

namespace make_binary_tree {

class Solution {
public:
    TreeNode * make_binary_tree(vector<int> &inOrder, vector<int> &postOrder) {
        //1 根据后续遍历找出中序遍历的切割点
        if (postOrder.size() == 0) {
            return NULL;
        }
        int root_value = postOrder[postOrder.size() - 1];
        TreeNode *root = new TreeNode(root_value);
        
        
        int sliceIndex = 0;
        for (sliceIndex = 0; sliceIndex < inOrder.size(); sliceIndex++) {
            if (inOrder[sliceIndex] == root_value) {
                break;
            }
        }
        
        // 2切个中序号数组,刚好切个成左右子树
        vector<int> left_in_order(inOrder.begin(),inOrder.begin() + sliceIndex);
        vector<int>right_in_order(inOrder.begin() + sliceIndex, inOrder.end());
        
        // 重置空间大小
        postOrder.resize(postOrder.size() - 1);
        
        // 这个是随便切的
        vector<int> left_post_order(postOrder.begin(),postOrder.begin() + left_in_order.size());
        vector<int> right_post_order(postOrder.begin() + left_in_order.size(), postOrder.end());
        
        // 递归完成左子树
        root->left = make_binary_tree(left_in_order, left_post_order);
        // 递归完成柚子树
        root->right = make_binary_tree(right_in_order, right_post_order);
        
        return root;
    }
    
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            if (inorder.size() == 0 || postorder.size() == 0) return NULL;
            return make_binary_tree(inorder, postorder);
    }
};

}

// 搜索树插入操作
namespace insert_binary_search_tree {

class Solution {
  
public:
    TreeNode * parent;
    
    Solution() {
        this->parent = new TreeNode(0);
    }
    
    void traversal_tree(TreeNode *node, int val) {
        if (node == NULL) {
            TreeNode *ele = new TreeNode(val);
            if (val > parent->right->val) {
                parent->right = ele;
                return;
            }
            parent->left = ele;
            return;
        }
        parent = node;
        if (val < node->left->val) {
            traversal_tree(node->left, val);
        }
        
        if (val > node->right->val) {
            traversal_tree(node->right, val);
        }
        return;
    }
    
    TreeNode * insert_bst(TreeNode *root, int val) {
        if (root == NULL) {
            return new TreeNode(val);
        }
        traversal_tree(root, val);
        return root;
    }
    
    ~Solution(){
        delete parent;
    }
};

class Solution1 {
    
public:
    
    TreeNode * insert_node(TreeNode *root, int val) {
        TreeNode * node = new TreeNode(val);
        if (root == NULL) {
            return node;
        }
        
        TreeNode *cur = root;
        TreeNode *parent = root;
        
        while (cur != NULL) {
            parent = cur;
            if (val < cur->left->val) {
                cur = cur->left;
            }
            
            if (val > cur->right->val ) {
                cur = cur->right;
            }
        }
        
        if (val < parent->val) {
            parent->left = node;
        } else {
            parent->right = node;
        }
        return root;
    }
    
};

}

namespace tree_delete_node {

class Solution {
    
public:
    TreeNode * node_delete(TreeNode *node, int val){
        // 1 没找到
        if (node == nullptr) {
            return node;
        }
        
        if (node->val == val) {
            // 找到节点删除
            // 2删除的是叶子节点
            if (node->left == nullptr && node->right == nullptr) {
                delete node;
                return nullptr;
            }
            
            // 3删除的节点的左子树为空, 右子树不为空
            if (node->left == nullptr && node->right) {
                TreeNode *temp = node->right;
                delete node;
                return temp;
            }
            
            // 4删除的左子树不为空,右子树为空
            if (node->left && node->right == nullptr) {
                TreeNode *temp = node->left;
                delete node;
                return temp;
            }
            
            // 左右子树都不为空, 找到右子树的最左侧节点,将删除节点的左子树拼接上
            if (node->left && node->right) {
                TreeNode *leftChild = node->left;
                TreeNode *rightChild = node->right;
                TreeNode *cur = node->right;
                
                while (cur) {
                    cur = cur->left;
                }

                cur->left = leftChild;
                
                delete node;
                return rightChild;
            }
            
        } else if (node->val > val) {
            //递归左子树
            node->left = node_delete(node->left, val);
        } else if (node->val < val) {
            //递归右子树
            node->right = node_delete(node->right, val);
        }
        
        return node;
    }
    
};

}

namespace both_node_grandfather {

class Solution {
  
public:
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        if (root->val == p->val || root->val == q->val || root == nullptr) {
            return root;
        }
        
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        
        if (left && right) {
            return root;
        } else if (left == nullptr && right) {
            return right;
        } else if (left && right == nullptr) {
            return left;
        }
        
        return nullptr;
    }
};

}


// 二叉搜索数的构造
namespace make_binary_search_tree {

class Solution {
    
public:
    
    TreeNode * traversal(vector<int> nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        
        int mid = left + (right - left) / 2;
        TreeNode *root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid - 1);
        root->right = traversal(nums, mid + 1, right);
        return root;
    }
    
    TreeNode * sortedArrayToBST(vector<int> array) {
        if (array.size() == 0) {
            return NULL;
        }
        
        TreeNode *root = traversal(array, 0, array.size()-1);
        return root;
    }
    
};

}

namespace tree_sum_bst {

class Solution {
  
public:
    int pre;
    void traversal(TreeNode *node) {
        if (node == nullptr) {
            return;
        }
        
        traversal(node->left);
        node->val += pre;
        pre = node->val;
        traversal(node->right);
    }
    
    TreeNode * sum_of_bst(TreeNode*root) {
        pre = 0;
        if (root == nullptr) {
            return nullptr;
        }
        traversal(root);
        return root;
    }
    
};

}

#endif /* tree_demo_hpp */
